home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / findrepl.swg / 0018_VERY FAST Boyer-Moore.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1993-11-21  |  10.3 KB  |  334 lines
  1. {
  2.   The originial benchmark program was to demonstrate the speed difference
  3.   between the POS() in Turbo Pascal 4 or 5 brute-force
  4.   and the Boyer-Moore method function POSBM()
  5.   Program author: Costas Menico
  6.  
  7.    Call: posbm(pat,buf,buflen);
  8.    or if you are using a string buffer:
  9.          posbm(pat,s[1],length(s));
  10. }
  11.  
  12. program bufSearch;
  13.  
  14. uses
  15.   dos, crt;
  16.  
  17.  
  18. {$F+}
  19. function posbm(pat:string; var buf; buflen:word):word; EXTERNAL;
  20. {$L BM.OBJ}
  21. {$F-}
  22.  
  23. function bruteForce(var such:string; var buf; buflen:word):word; ASSEMBLER;
  24. ASM
  25.         cld
  26.         push ds
  27.         les        di,buf
  28.         mov        cx,buflen
  29.         jcxz @@30
  30.         lds        si,such
  31.         mov  al,[si]
  32.         or   al,al
  33.         je   @@30
  34.         xor  ah,ah
  35.         cmp  ax,cx
  36.         ja   @@30
  37.         mov  bx,si
  38.         dec  cx
  39.   @@10:
  40.         mov  si,bx
  41.         lodsw
  42.         xchg al,ah          { AH=Stringlänge, AL=Suchchar }
  43.         repne scasb
  44.         jne  @@30
  45.         dec  ah
  46.         or   ah,ah
  47.         je   @@20
  48.  
  49.         inc  cx             { CX++ nach rep... }
  50.         xchg cx,ax
  51.         mov  cl,ch
  52.         xor  ch,ch
  53.         mov  dx,di
  54.         repe        cmpsb
  55.         mov  di,dx
  56.         mov  cx,ax
  57.         loopne @@10
  58.   @@20:
  59.         mov  ax,buflen
  60.         sub  ax,cx
  61.         dec  ax
  62.         jmp  @@40
  63.   @@30:
  64.         xor  ax,ax
  65.   @@40:
  66.         pop  ds
  67. end;
  68.  
  69.  
  70.  
  71. procedure showtime(s : string; t : registers);
  72.  
  73. begin
  74.   writeln(s, ' Hrs:', t.ch, ' Min:', t.cl, ' Sec:', t.dh, ' Milsec:', t.dl);
  75. end;
  76.  
  77. var
  78.   pat    : string;
  79.   i,
  80.   j      : integer;
  81.   start,
  82.   finish : registers;
  83.   arr    : array[1..4096] of char;
  84.  
  85. const
  86.   longloop = 5000;
  87.  
  88. begin
  89.   clrscr;
  90.   randomize;
  91.   for i := 1 to 4096 do
  92.     arr[i] := chr(random(255)+1);
  93.  
  94.   move(arr[4090],pat[1],5); pat[0]:=#5;
  95.  
  96.   writeln('Search using Brute-Force Method <please wait>');
  97.   start.ah := $2C;
  98.   msdos(start);
  99.   for j := 1 to longloop do
  100.     i := bruteForce(pat,arr,4096);
  101.   finish.ah := $2C;
  102.   msdos(finish);
  103.   showtime('Start  ', start);
  104.   showtime('Finish ', finish);
  105.   writeln('Pattern found at position ', i);
  106.   writeln;
  107.   writeln('Search using Boyer-Moore Method <please wait>');
  108.   start.ah := $2C;
  109.   msdos(start);
  110.   for j := 1 to longloop do
  111.     i := posbm(pat, arr,4096);
  112.   finish.ah := $2C;
  113.   msdos(finish);
  114.   showtime('Start  ', start);
  115.   showtime('Finish ', finish);
  116.   writeln('Pattern found at position ', i);
  117.   writeln;
  118.   writeln('Done ... Press Enter');
  119.   readln;
  120. end.
  121.  
  122. { --------------------------   XX34 OBJECT CODE  ----------------------- }
  123. { ------------------------- CUT OUT AND SAVE AS BM.XX  ------------------}
  124. { ------------------------  USE XX3401 D BM.XX   ------------------------}
  125.  
  126. *XX3401-000392-050693--68--85-03573----------BM.OBJ--1-OF--1
  127. U-M+32AuL3--IoB-H3l-IopQEYoiEJBBYcUU++++53FpQa7j623nQqJhMalZQW+UJaJm
  128. QqZjPW+n9X8NW-k+ECbfXgIO32AuL3--IoB-H3l-IopQEYoiEJBB+sU1+21dH7M0++-c
  129. W+A+E84IZUM+-2BDF2J3a+Q+OCQ++U2-1d+A+++--J-DIo7B++++rMU2+20W+N4Uuk+-
  130. ++-JUSkA+Mjg5X9YzAKq4+4AbUM-f+f+REDdjU09m6Z4+6aq-+53hVE-X7s8+Mi42U29
  131. k5I1uO6+WIM0WPM6+MDt+LIPlPM2+On2jUU-Wos0weto+ya1+6jrUys0uqyEXLs2XB8C
  132. kcd4+6fUiM++wuj3hUE-XJs2Wos+GMjRXKs2AiGgWzW60y9tf6jsW+i9uwKq0+4BTUG9
  133. JU78WoM+G19zzGjEQXE1w6cQBcc-0g-pwMjSWos+l9s2+Iw1yTCaR+ms+E0BTUG9wn9z
  134. uxK9lgKq0+2flUI0+Cg0Aw1w5sjZUQEA+Jr80U-fWU6++5E+
  135. ***** END OF XX-BLOCK *****
  136.  
  137. { --------------------------   ASSEMBLER CODE  ------------------------- }
  138. { ------------------------- CUT OUT AND SAVE AS BM.AMS ------------------}
  139. { ------------------------  USE TASM TO ASSEMBLE ------------------------}
  140.  
  141. ; filename: BM.ASM
  142. ; fast search routine to search strings in ARRAYS OF CHARS
  143. ; function in Turbo Pascal >= 4. Based on the Boyer-Moore algorithm.
  144. ; program author: Costas Menico.
  145. ; Very small modifications for using an ARRAY OF CHAR buffer instead of
  146. ; a string made by Jochen Magnus in May 93.
  147. ; declare as follows:
  148. ; {$F+}
  149. ; {$L BM.OBJ}
  150. ; function posbm(pat:string; var buffer; buflen:word):WORD; external;
  151. ; call as follows from Turbo 4..7:
  152. ; location := posbm(pat, buf, buflen);
  153. ; call for a search in a string typed buffer:
  154. ; location := posbm(pat, str[1], length(str));
  155.  
  156.  
  157. skiparrlength        equ        256
  158.  
  159. ; function work stack
  160.  
  161. dstk                struc
  162. patlen                dw        ?
  163. strlen                dw        ?
  164. skiparr                db        skiparrlength dup(?)
  165. pattxt                dd        0
  166. strtxt                dd        0
  167. dstk                ends
  168.  
  169. ; total stack (callers plus work stack)
  170.  
  171. cstk                struc
  172. ourdata                db        size dstk dup(?)
  173. bpsave                dw        0
  174. retaddr                dd        0
  175. paramlen       dw   0                                                           ; JO
  176. straddr                dd        0
  177. pataddr                dd        0
  178. cstk                ends
  179.  
  180. paramsize        equ        size pataddr+size straddr +size paramlen           ; +2  JO
  181.  
  182. code                segment        para public
  183.                 assume cs:code
  184.  
  185. ; entry point to posbm function
  186.  
  187. posbm                proc        far
  188.                 public        posbm
  189.  
  190.                 push        bp
  191.                          sub        sp, size dstk
  192.                          mov        bp, sp
  193.                          push    ds
  194.                          xor        ah, ah
  195.                          cld
  196.  
  197. ; get and save the length and address of the pattern
  198.  
  199.                 lds        si, [bp.pataddr]
  200.                          mov        word ptr [bp.pattxt][2], ds
  201.                          lodsb
  202.                          or        al, al
  203.                          jne        notnullp
  204.                          jmp        nomatch
  205.  
  206. notnullp:
  207.                 mov        cx, ax
  208.                          mov        [bp.patlen], ax
  209.                          mov        word ptr [bp.pattxt], si
  210.  
  211. ; get and save the length and address of the string text
  212.  
  213.                 lds        si, [bp.straddr]
  214.                          mov        word ptr [bp.strtxt][2], ds
  215.                          mov ax,[bp.paramlen]                                          ; JO
  216.                          or  ax,ax                                                              ; JO
  217.                          jne        notnulls
  218.                          jmp        nomatch
  219.  
  220. notnulls:
  221.                 mov        [bp.strlen], ax
  222.                          mov        word ptr [bp.strtxt], si
  223.                          cmp        cx, 1
  224.                          jne        do_boyer_moore
  225.                          lds        si, [bp.pattxt]
  226.                          lodsb
  227.                          les        di, [bp.strtxt]
  228.                          mov        cx, [bp.strlen]
  229.                          repne        scasb
  230.                          jz        match1
  231.                          jmp        nomatch
  232.  
  233. match1:
  234.                 mov        si, di
  235.                          sub        si, 2
  236.                          jmp        exactmatch
  237.  
  238. do_boyer_moore:
  239.  
  240. ; fill the ASCII character skiparray with the
  241. ; length of the pattern
  242.  
  243.                 lea        di, [bp.skiparr]
  244.                          mov        dx, ss
  245.                          mov        es, dx
  246.                          mov        al, byte ptr [bp.patlen]
  247.                          mov        ah, al
  248.                          mov        cx, skiparrlength/2
  249.                          rep        stosw
  250.  
  251. ; replace in the ASCII skiparray the corresponding
  252. ; character offset from the end of the pattern minus 1
  253.  
  254.                 lds        si, [bp.pattxt]
  255.                          lea        bx, [bp.skiparr]
  256.                          mov        cx, [bp.patlen]
  257.                          dec        cx
  258.                          mov        bx, bp
  259.                          lea        bp, [bp.skiparr]
  260.                          xor        ah, ah
  261.  
  262. fill_skiparray:
  263.                 lodsb
  264.                          mov        di, ax
  265.                          mov        [bp+di], cl
  266.                          loop        fill_skiparray
  267.                          lodsb
  268.                          mov        di, ax
  269.                          mov        [bp+di], cl
  270.                          mov        bp, bx
  271.  
  272. ; now initialize our pattern and string text pointers to
  273. ; start searching
  274.  
  275.                 lds        si, [bp.strtxt]
  276.                          lea        di, [bp.skiparr]
  277.                          mov        dx, [bp.strlen]
  278.                          dec        dx
  279.                          mov        ax, [bp.patlen]
  280.                          dec        ax
  281.                          xor        bh, bh
  282.                          std
  283.  
  284. ; get character from text. use the character as an index
  285. ; into the skiparray, looking for a skip value of 0.
  286. ; if found, execute a brute-force search on the pattern
  287.  
  288. searchlast:
  289.                 sub        dx, ax
  290.                          jc        nomatch
  291.                          add        si, ax
  292.                          mov        bl, [si]
  293.                          mov        al, ss:[di+bx]
  294.                          or        al, al
  295.                          jne        searchlast
  296.  
  297. ; we have a possible match, therefore
  298. ; do the reverse brute-force compare
  299.  
  300.                 mov        bx, si
  301.                          mov        cx, [bp.patlen]
  302.                          les        di, [bp.pattxt]
  303.                          dec        di
  304.                          add        di, cx
  305.                          repe        cmpsb
  306.                          je        exactmatch
  307.                          mov        ax, 1
  308.                          lea        di, [bp.skiparr]
  309.                          mov        si, bx
  310.                          xor        bh, bh
  311.                          jmp        short searchlast
  312.  
  313. exactmatch:
  314.                 mov        ax, si
  315.                          lds        si, [bp.strtxt]
  316.                          sub        ax, si
  317.                          add        ax, 2
  318.                          jmp        short endsearch
  319.  
  320. nomatch:
  321.                 xor        ax, ax
  322.  
  323. endsearch:
  324.                 cld
  325.                          pop        ds
  326.                          mov        sp, bp
  327.                          add        sp, size dstk
  328.                          pop        bp
  329.                          ret        paramsize
  330. posbm                endp
  331.  
  332. code                ends
  333.                 end
  334. {-----------------------   END OF ASSEMBLER CODE -------------------------}